package com.chj.lintcode.backpack;

// https://leetcode.com/problems/combination-sum-iv/discuss/85036/1ms-Java-DP-Solution-with-Detailed-Explanation
public class Code06_CombinationSumIv {
	/**
	 * @param nums: an integer array and all positive numbers, no duplicates
	 * @param target: An integer
	 * @return: An integer
	 */
//	public static int backPackVI(int[] nums, int target) {
//		// write your code here
//		int n = nums.length;
//		int[][] dp = new int[n + 1][target + 1];
//		dp[0][0] = 1;
//
//		for (int i = 1; i <= target; i++) {
//			dp[0][i] = 0;
//		}
//
//		for (int i = 1; i <= n; i++) {
//			for (int j = 0; j <= target; j++) {
//				dp[i][j] = dp[i - 1][j];
//				if (j >= nums[i - 1]) {
//					dp[i][j] += dp[i - 1][j - nums[i - 1]];
//				}
//			}
//		}
//
//		return dp[n][target];
//	}

	public static int combinationSum4(int[] nums, int target) {
		if (target == 0) {
			return 1;
		}
		int res = 0;
		for (int i = 0; i < nums.length; i++) {
			if (target >= nums[i]) {
				res += combinationSum4(nums, target - nums[i]);
			}
		}
		return res;
	}

	public static int combinationSum4Dp(int[] nums, int target) {
		int[] dp = new int[target + 1];
//		if (target == 0) {
//			return 1;
//		}
		dp[0] = 1;
//		int res = 0;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < nums.length; j++) {
				if (i >= nums[j]) {
//				res += combinationSum4(nums, target - nums[i]);
					dp[i] += dp[i - nums[j]];
				}
			}
		}
		return dp[target];
	}
}
